package com.zjsru.oneday202208;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/9/6
 * 统计子串中的唯一字符
 *
 * 输入: s = "ABC"
 * 输出: 10
 * 解释: 所有可能的子串为："A","B","C","AB","BC" 和 "ABC"。
 *      其中，每一个子串都由独特字符构成。
 *      所以其长度总和为：1 + 1 + 1 + 2 + 2 + 3 = 10
 *
 */
public class UniqueLetterString {
    public int uniqueLetterString(String s) {
        int ans = 0;
        char[] cs = s.toCharArray();
        int n = s.length();
        int[] l = new int[n], r = new int[n];
        int[] idx = new int[26];
        Arrays.fill(idx,-1);
        for (int i = 0; i < n; i++) {
            int u = cs[i] - 'A';
            l[i] = idx[u];
            idx[u] = i;
        }
        Arrays.fill(idx,n);
        for (int i = n - 1; i >= 0 ; i--) {
            int u = cs[i] - 'A';
            r[i] = idx[u];
            idx[u] = i;
        }
        for (int i = 0; i < n; i++) {
            ans += (i - l[i])*(r[i] - i);
        }
        return ans;
    }
    
    public static void main(String[] args) {
        UniqueLetterString uniqueLetterString = new UniqueLetterString();
        String s = "ABC";
        System.out.println(uniqueLetterString.uniqueLetterString(s));
    }
}
